package cn.mjc.game.sudoku;

/**
 * Exhaustive algorithm to resolve the NPalace.
 * <P/>
 * The core concept of this algorithm is to fill each blank with all possibility
 * value and find the first result.The step of this algorithm is:<br/>
 * <ul>
 * <li>find all blanks and remember them.</li>
 * <li>get a blank and compute the value range for it.</li>
 * <li>if the value range is null and the blank is the first,that means there is
 * no solution for current NPalace.</li>
 * <li>if the value range is null and the blank is not fist,that means the
 * previous blank was put wrong value,then roll back to the previous blank and
 * put the next value of value range of that blank.</li>
 * <li>if the value range is not null,then get the first value and set to this
 * blank,then to the next blank and repeat the step 2.</li>
 * <li>if there are no next blank means resolve over and the answer is come out.
 * </li>
 * </ul>
 * 
 * @author EricMa
 * 
 */
public class ExhaustiveNResolver extends AbstractNResolver {

	public ExhaustiveNResolver(NPalace npalace) {
		super(npalace);
	}

	@Override
	public int[][] resolve(NPalace npalace) {
		int[][] result = npalace.getUserValues();
		if (!resolveCellByCell(result))
			result = null;
		return result;
	}

	/**
	 * to resolve the NPalace cell by cell.
	 * 
	 * @param data
	 * @return false means no answer
	 */
	private boolean resolveCellByCell(int[][] data) {
		// remember all blank cell
		int[][] blanks = new int[npalace.getCellSize() * npalace.getCellSize()][];
		int blankSize = 0;
		for (int x = 0; x < npalace.getCellSize(); x++) {
			for (int y = 0; y < npalace.getCellSize(); y++) {
				if (data[x][y] > 0)
					continue; // have value
				blanks[blankSize++] = new int[] { x, y };
			}
		}
		if (blankSize == 0 || blankSize == blanks.length)
			return false; // no blank or all is blank
		return recurseCellByCell(data, blanks, 0);
	}

	private boolean recurseCellByCell(int[][] data, int[][] blanks, int blankIndex) {
		int[] coor = blanks[blankIndex];
		if (coor == null)
			return true; // not a blank,is the last blank
		int[] range = this.getValueRange(data, coor[0], coor[1]);
		if (range == null)
			return false; // previous blank set wrong value,should roll back
		boolean success = false;
		for (int i = 0; i < range.length; i++) {
			data[coor[0]][coor[1]] = range[i];
			if (recurseCellByCell(data, blanks, blankIndex + 1)) {
				success = true;
				break;
			}
		}
		if (!success)
			data[coor[0]][coor[1]] = 0;
		return success;
	}
}
